// 2015年版权所有etcd作者
// 
// 根据Apache许可证2.0版（以下简称“许可证”）获得许可；
// 除非遵守许可证，否则不得使用此文件。
// 您可以通过
// 
// www.apache.org/licenses/LICENSE-2.0 
// 
// 除非适用法律要求或书面同意，否则根据许可证分发的软件
// 按“原样”分发，
// 无任何明示或暗示的保证或条件。
// 请参阅许可证，了解管理许可的特定语言和
// 许可证下的限制。

package raft

import (
	"fmt"
	"log"

	pb "go.etcd.io/etcd/raft/v3/raftpb"
)

type raftLog struct {
	storage Storage	// MemoryStorage实例，其中存储了快照数据及该快照之后的En位y记录
	unstable unstable	// 用于存储未写入Storage的快照数据及Entry记录
	committed uint64	// 己提交的位置，即己提交的Entry记录中最大的索引值。
	applied uint64	// 己应用的位置，即己应用的Entry记录中最大的索引值,其中committed和applied之间始终满足committed<=applied这个不等式关系。
	logger Logger
	maxNextEntsSize uint64	// 从调用nextEnts返回的消息最大聚合字节数。
}

// 创建一个raftLog实例
// newLog使用给定的存储和默认选项返回日志。它将日志恢复到它刚刚提交的状态，并应用最新的快照。
func newLog(storage Storage, logger Logger) *raftLog {
	return newLogWithSize(storage, logger, noLimit)
}

// 创建一个raftLog实例
func newLogWithSize(storage Storage, logger Logger, maxNextEntsSize uint64) *raftLog {
	if storage == nil {
		log.Panic("storage must not be nil")
	}
	log := &raftLog{	// 创建raftLog实例，并初始化storage字段
		storage:         storage,
		logger:          logger,
		maxNextEntsSize: maxNextEntsSize,
	}
	// 获取Storage中的第一条Entry和最后一条Entry的索引佳
	firstIndex, err := storage.FirstIndex()
	if err != nil {
		panic(err) // TODO（bdarnell）
	}
	lastIndex, err := storage.LastIndex()
	if err != nil {
		panic(err) // TODO（bdarnell）
	}
	// 4月古古f匕unstable.offset
	log.unstable.offset = lastIndex + 1
	log.unstable.logger = logger
	// ／初始化committed、applied字段
	log.committed = firstIndex - 1
	log.applied = firstIndex - 1

	return log
}

func (l *raftLog) String() string {
	return fmt.Sprintf("committed=%d, applied=%d, unstable.offset=%d, len(unstable.Entries)=%d", l.committed, l.applied, l.unstable.offset, len(l.unstable.entries))
}

// 如果无法追加条目，则可能返回（0，false）。否则，返回（新条目的最后一个索引，true）。
// raftLog.maybeAppend（）方法的大致步骤如下。
// ( 1 ) maybeAppend（）方法的参数：
// 第一个参数index是MsgApp消息携带的第一条Entry的Index值，
// 这里的MsgApp消息是etcd-raft模块中定义的消息类型之一，
// 对应Raft协议中提到的Append Entries消息；
// 第二个参数logTerm是MsgApp消息的LogTerm宇段，
// 通过消息中携带的该Term值与当前节点记录的Term进行比较，
// 就可以判断消息是否为过时的消息：
// 第三个参数committed是MsgApp消息的Commit宇段，
// Leader节点通过该字段通知Follower节点当前己提交Entry的位置；
// 第四个参数ents是MsgApp消息中携带的Entry记录，
// 即待追加到raftLog中的En盯f记录。
// ( 2) maybeAppend（）方法首先会调用matchTerm（）方法检测MsgApp消息的Index宇段及Log Term字段是否合法
func (l *raftLog) maybeAppend(index, logTerm, committed uint64, ents ...pb.Entry) (lastnewi uint64, ok bool) {
	if l.matchTerm(index, logTerm) {	// 检测MsgApp消息的Index宇段及Log Term字段是否合法
		lastnewi = index + uint64(len(ents))
		ci := l.findConflict(ents)
		switch {
		case ci == 0:	// findConflict （）方法返回0时，表示raftLog中已经包含了所有待追加的Entry记录，不必进行任何追加操作
		case ci <= l.committed:	// 如采出现冲突的位置是己提交的记录，则输出异常日志并终止整个程序
			l.logger.Panicf("entry %d conflict with committed entry [committed(%d)]", ci, l.committed)
		default:	// 如果冲突位置是未提交的部分
			offset := index + 1
			l.append(ents[ci-offset:]...)	// 则将ents中未发生冲突的部分追加到raftLog中
		}
		l.commitTo(min(committed, lastnewi))
		return lastnewi, true
	}
	return 0, false
}

// raftLog.append（）方法主要通过调用unstable.truncateAndAppend（）方法完成记录的追加功能，
func (l *raftLog) append(ents ...pb.Entry) uint64 {
	// 合法性检测
	if len(ents) == 0 {
		return l.lastIndex()
	}
	if after := ents[0].Index - 1; after < l.committed {
		l.logger.Panicf("after(%d) is out of range [committed(%d)]", after, l.committed)
	}
	// 调用unstable.truncateAndAppend（）方法将Entry记录追加到unstable中
	l.unstable.truncateAndAppend(ents)
	return l.lastIndex()	// 返回raftLog最后一条日志记录的索引
}

// 遍历待追加的Entry集合，查找是否与raftLog中己有的Entry发生冲突（Index相同但Term不同）
// 需要注意findConflict（）方法的返回值：当待追加的Enty记录在raftLog中不存在时，
// 会返回第一条不存在Entry记录的索引值；raftLog包含全部的待追加记录且没有发生冲突，则返回0
func (l *raftLog) findConflict(ents []pb.Entry) uint64 {
	// 追历全部待追加的Entry，判断raftLog中是否存在冲突的Entry记录
	for _, ne := range ents {
		if !l.matchTerm(ne.Index, ne.Term) {	// 查找冲突的Entry记录
			if ne.Index <= l.lastIndex() {
				l.logger.Infof("found conflict at index %d [existing term: %d, conflicting term: %d]",
					ne.Index, l.zeroTermOnErrCompacted(l.term(ne.Index)), ne.Term)
			}
			return ne.Index	// 返回冲突记录的索引位
		}
	}
	return 0	// 如果没有发生冲突Entry,则返回0。
}

// findConflictByTerm获取（索引，术语）对（表示追加期间引线/跟随器上的冲突日志
// 条目），并在
// 日志l中查找最大的索引，其中术语<=`term`和索引<=`index`。如果日志中不存在这样的索引
// 则返回日志的第一个索引。
// 
// 提供的索引必须等于或小于l.lastIndex（）。无效的
// 输入记录警告并返回输入索引。
func (l *raftLog) findConflictByTerm(index uint64, term uint64) uint64 {
	if li := l.lastIndex(); index > li {
		// NB：这样的调用不应该存在，但既然有一种直接的恢复方法，那就这样做吧。
		// 
		// 也很想检查第一个索引，但
		// 在没有日志的对等方中存在奇怪的行为，在这种情况下，
		// lastIndex将返回零，firstIndex将返回一，其中
		// 导致对该方法进行索引为零的调用。
		l.logger.Warningf("index(%d) is out of range [0, lastIndex(%d)] in findConflictByTerm",
			index, li)
		return index
	}
	for {
		logTerm, err := l.term(index)
		if logTerm <= term || err != nil {
			break
		}
		index--
	}
	return index
}

func (l *raftLog) unstableEntries() []pb.Entry {
	if len(l.unstable.entries) == 0 {
		return nil
	}
	return l.unstable.entries
}

// nextEnts返回所有可执行的条目。
// 如果应用小于快照索引，则返回快照索引后所有提交的
// 条目。
func (l *raftLog) nextEnts() (ents []pb.Entry) {
	off := max(l.applied+1, l.firstIndex())	// 获取当前已经反用记录的位置
	if l.committed+1 > off {	// 是否存在已提交且未应用的Entry记录
		// 获取全部已提交且未应用的Entry记录并返回
		ents, err := l.slice(off, l.committed+1, l.maxNextEntsSize)
		if err != nil {
			l.logger.Panicf("unexpected error when getting unapplied entries (%v)", err)
		}
		return ents
	}
	return nil
}

// 当上层模块需要从raftLog获取Entry记录进行处理时，会先调用hasNextEnts（）方法检测是否有待应用的记录，
// 然后调用nextEnts（）方法将己提交且未应用的Entry记录返回给上层模块处理
func (l *raftLog) hasNextEnts() bool {
	off := max(l.applied+1, l.firstIndex())	// 获取当前已经反用记录的位置
	return l.committed+1 > off	// 是否存在已提交且未应用的Entry记录
}

// 如果有挂起的快照等待应用，则返回hasPendingSnapshot。
func (l *raftLog) hasPendingSnapshot() bool {
	return l.unstable.snapshot != nil && !IsEmptySnap(*l.unstable.snapshot)
}

func (l *raftLog) snapshot() (pb.Snapshot, error) {
	if l.unstable.snapshot != nil {
		return *l.unstable.snapshot, nil
	}
	return l.storage.Snapshot()
}

// 返回的是raftLog中第一条Entry记录的索引值。先尝试通过unstable.maybeFirstindex（）方法进行查找，
// 如果查找失败，则通过Storage.Firstlndex（）方法进行查找。
func (l *raftLog) firstIndex() uint64 {
	if i, ok := l.unstable.maybeFirstIndex(); ok {
		return i
	}
	index, err := l.storage.FirstIndex()
	if err != nil {
		panic(err) // TODO（bdarnell）
	}
	return index
}

// 返回的是raftLog中最后一条Entry记录的索引值。先尝试通过maybeLastlndex（）方法进行查找，
//如果查找失败，则通过Lastlndex（）方法进行查找。
func (l *raftLog) lastIndex() uint64 {
	if i, ok := l.unstable.maybeLastIndex(); ok {
		return i
	}
	i, err := l.storage.LastIndex()
	if err != nil {
		panic(err) // TODO（bdarnell）
	}
	return i
}

// 更新raftLog.committed宇段
func (l *raftLog) commitTo(tocommit uint64) {
	// raftLog.committed字段只能后移，不能前移
	if l.committed < tocommit {
		if l.lastIndex() < tocommit {
			l.logger.Panicf("tocommit(%d) is out of range [lastIndex(%d)]. Was the raft log corrupted, truncated, or lost?", tocommit, l.lastIndex())
		}
		l.committed = tocommit	// 更新committed字段
	}
}

func (l *raftLog) appliedTo(i uint64) {
	if i == 0 {
		return
	}
	if l.committed < i || i < l.applied {
		l.logger.Panicf("applied(%d) is out of range [prevApplied(%d), committed(%d)]", i, l.applied, l.committed)
	}
	l.applied = i
}

func (l *raftLog) stableTo(i, t uint64) { l.unstable.stableTo(i, t) }

func (l *raftLog) stableSnapTo(i uint64) { l.unstable.stableSnapTo(i) }

func (l *raftLog) lastTerm() uint64 {
	t, err := l.term(l.lastIndex())
	if err != nil {
		l.logger.Panicf("unexpected error when getting the last term (%v)", err)
	}
	return t
}

// ra位Log.term（）方法先会去unstable中查找相应的Entry记录，如果查找不到，则再去storage中查找
func (l *raftLog) term(i uint64) (uint64, error) {
	// 检测指定的索引值的合法性
	dummyIndex := l.firstIndex() - 1
	if i < dummyIndex || i > l.lastIndex() {
		// TODO:返回错误？
		return 0, nil
	}
	// 尝试从unstable中获取对应的Entry记录并返回其Term值
	if t, ok := l.unstable.maybeTerm(i); ok {
		return t, nil
	}
	// 尝试从storage中获取对应的Entry记录并返回其Termf直
	t, err := l.storage.Term(i)
	if err == nil {
		return t, nil
	}
	if err == ErrCompacted || err == ErrUnavailable {
		return 0, err
	}
	panic(err) // TODO（bdarnell）
}

// raftLog.entries（）方法获取指定的Entry记录
// 在Leader节点向Follower节点发送MsgApp消息时，
// 需要根据Follower节点的日志复制(Nextlndex和Matchlndex）情况决定发送的Entry记录，此时需要调用
func (l *raftLog) entries(i, maxsize uint64) ([]pb.Entry, error) {
	// 检测指定的Entry记录索引值是否超出了raftLog的范围
	if i > l.lastIndex() {
		return nil, nil
	}
	// 获取指定范围的Entry记录
	return l.slice(i, l.lastIndex()+1, maxsize)
}

// allEntries返回日志中的所有条目。
func (l *raftLog) allEntries() []pb.Entry {
	ents, err := l.entries(l.firstIndex(), noLimit)
	if err == nil {
		return ents
	}
	if err == ErrCompacted { // 如果发生赛车压缩，请重试
		return l.allEntries()
	}
	// TODO（香格里）：处理错误？
	panic(err)
}

// 比较日志的新旧程度
// Follower节点在接收到Candidate节点的选举请求之后，
// 会通过比较Candidate节点的本地日志与自身本地日志的新旧程度，从而决定是否投票。
// 首先注意一下参数，lasti和term分别是Candidate节点的最大记录索引值和最大任期号（即MsgVote
// 请求（Candidate发送的选举请求）携带的Index和LogTerm)
func (l *raftLog) isUpToDate(lasti, term uint64) bool {
	// 比较日志新旧的方式，先比较任期号，任其月号相同时再比较索引值
	return term > l.lastTerm() || (term == l.lastTerm() && lasti >= l.lastIndex())
}

// 检测MsgApp消息的Index宇段及Log Term字段是否合法
func (l *raftLog) matchTerm(i, term uint64) bool {
	t, err := l.term(i)	// 查询指定索引位对应的Entry记录的Term佳
	if err != nil {
		return false
	}
	return t == term
}

func (l *raftLog) maybeCommit(maxIndex, term uint64) bool {
	if maxIndex > l.committed && l.zeroTermOnErrCompacted(l.term(maxIndex)) == term {
		l.commitTo(maxIndex)
		return true
	}
	return false
}

func (l *raftLog) restore(s pb.Snapshot) {
	l.logger.Infof("log [%s] starts to restore snapshot [index: %d, term: %d]", l, s.Metadata.Index, s.Metadata.Term)
	l.committed = s.Metadata.Index
	l.unstable.restore(s)
}

// slice返回从lo到hi-1（含）的日志条目片段。
func (l *raftLog) slice(lo, hi, maxSize uint64) ([]pb.Entry, error) {
	// 边界检测，检测的条件是l.firstindex () <= lo < hi <= l. lastindex ()
	err := l.mustCheckOutOfBounds(lo, hi)
	if err != nil {
		return nil, err
	}
	if lo == hi {
		return nil, nil
	}
	var ents []pb.Entry
	// 如采lo小于unstable.offset(unstable中第一条记录的索引），则需妾从raftLog.storage中获取记录
	if lo < l.unstable.offset {
		// 从Storage中获取记录，可能只能从Storage中取前半部分（也就是到lo~l.unstable.offset 部分)
		// 注意maxSize参数，它会限制获取的记录切片的总字节数
		storedEnts, err := l.storage.Entries(lo, min(hi, l.unstable.offset), maxSize)
		if err == ErrCompacted {
			return nil, err
		} else if err == ErrUnavailable {
			l.logger.Panicf("entries[%d:%d) is unavailable from storage", lo, min(hi, l.unstable.offset))
		} else if err != nil {
			panic(err) // TODO（bdarnell）
		}

		// 从Storage中取出的记录已经达到了maxSize的上限，则立接返回
		if uint64(len(storedEnts)) < min(hi, l.unstable.offset)-lo {
			return storedEnts, nil
		}

		ents = storedEnts
	}
	// 从unstable中取出后半部分记录，即l.unstable.offset～hi的日志记录
	if hi > l.unstable.offset {
		unstable := l.unstable.slice(max(lo, l.unstable.offset), hi)
		// 将Storage中获取的记录与unstable中获取的记录进行合并
		if len(ents) > 0 {
			combined := make([]pb.Entry, len(ents)+len(unstable))
			n := copy(combined, ents)
			copy(combined[n:], unstable)
			ents = combined
		} else {
			ents = unstable
		}
	}
	// 限制获取的记录切片的总字节数
	return limitSize(ents, maxSize), nil
}

// l.firstIndex<=lo<=hi<=l.firstIndex+len（l.entries）
func (l *raftLog) mustCheckOutOfBounds(lo, hi uint64) error {
	if lo > hi {
		l.logger.Panicf("invalid slice %d > %d", lo, hi)
	}
	fi := l.firstIndex()
	if lo < fi {
		return ErrCompacted
	}

	length := l.lastIndex() + 1 - fi
	if hi > fi+length {
		l.logger.Panicf("slice[%d,%d) out of bound [%d,%d]", lo, hi, fi, l.lastIndex())
	}
	return nil
}

func (l *raftLog) zeroTermOnErrCompacted(t uint64, err error) uint64 {
	if err == nil {
		return t
	}
	if err == ErrCompacted {
		return 0
	}
	l.logger.Panicf("unexpected error (%v)", err)
	return 0
}
